
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/*
 * @lc app=leetcode.cn id=239 lang=java
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
//初始情况,把属猪nums的前k个元素放入优先队列,当我们向右边移动窗口
//就可以把一个新的元素放入优先队列中,此时堆顶的元素就是堆中所有元素的最大值.
// 然而这个最大值可能并不在滑动窗口中,
// 这种情况下,这个值在数组nums中的位置在当前滑动窗口的左边界的左侧
// 因此,后续向右边移动窗口时,这个值可能永远不会出现在滑动窗口中,可以永久将其从滑动窗口删除
// 不断地移除堆顶的元素,直到他确实出现在滑动窗口中
// 在优先队列中存储二元组(num,index),表示元素num在数组中下标为index
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1];
            }

        });
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(new int[] { nums[i], i });
        }
        int[] ans = new int[n - k + 1];// 前k个有一个根节点,后面n-k次每次一个根节点
        ans[0] = priorityQueue.peek()[0];

        for (int i = k; i < n; i++) {
            priorityQueue.offer(new int[] { nums[i], i });
            while (priorityQueue.peek()[1] <= i - k) {// 比较堆顶节点的顺序和当前滑动窗口的起始索引
                priorityQueue.poll();
            }
            ans[i - k + 1] = priorityQueue.peek()[0];

        }
        return ans;
    }
}
// @lc code=end

// [1,-1]
// 1